class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        unordered_set<string> has;
        for(string& s:wordDict)
        {
            has.insert(s);
        }
        s=' '+s;
        vector<bool> dp(s.size()+1,false);
        dp[0]=true;
        for(int i=1;i<=s.size();i++)
        {
            for(int j=1;j<=i;j++)
            {
                if(dp[j-1] && has.count(s.substr(j,i-j+1)))
                {
                    dp[i]=true;
                    break;
                }
            }
        }
        return dp[s.size()-1];
    }
};
